package com.fwpsl.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author: 风戏fw
 * @date: 2024/2/22
 * @description: 快速排序是一种非常高效的排序算法，它采用分而治之（Divide and Conquer）的策略来将一个数组排序。
 * 基本思想是通过一次排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * <p>
 * 快速排序的平均时间复杂度为 O(n log n)，但在最坏情况下（例如数组已经是有序的），其时间复杂度会退化到 O(n^2)。
 * 为了避免最坏情况的发生，在实际应用中通常会采用一些优化策略，比如随机选择基准值或者使用三数取中法来选择基准值。
 */
public class QuickSort {

    public static void quickSort(int[] arr) {
        qsort(arr, 0, arr.length - 1);
    }

    private static void qsort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        //将数组分为两部分
        int pivot = partition(arr, low, high);
        //递归排序左子数组
        qsort(arr, low, pivot - 1);
        //递归排序右子数组
        qsort(arr, pivot + 1, high);
    }

    /**
     * 快速排序 - 随机选择基准值
     */
    private static int randomPatition(int[] arr, int low, int high) {
        int index = new Random().nextInt(high - low + 1) + low;
        if (index != low) {
            int temp = arr[index];
            arr[index] = arr[low];
            arr[low] = temp;
        }
        return partition(arr, low, high);
    }

    /**
     * 快速排序 - 三数取中法来选择基准值, 仅在low、mid、hight三个下标对应的值有序时，使用三数取中法。
     */
    private static int medianOfThreePatition(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;

        // 仅在low、mid、hight三个下标对应的值有序时，使用三数取中法。
        if (arr[low] < arr[mid] && arr[mid] < arr[high]) {
            int temp = arr[mid];
            arr[mid] = arr[low];
            arr[low] = temp;
        }
        return partition(arr, low, high);
    }

    private static int partition(int[] arr, int low, int high) {
        //基准
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                --high;
            }
            //交换比基准大的记录到左端
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) {
                ++low;
            }
            //交换比基准小的记录到右端
            arr[high] = arr[low];
        }
        //扫描完成，基准到位
        arr[low] = pivot;
        //返回的是基准的位置
        return low;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{15, 38, 84, 11, 3, 38, 91, 13, 65, 49, 43};
        System.out.println("before sort:" + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("after sort:" + Arrays.toString(arr));
    }
}
